package priorityqueue;

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class Heap {
    public int[] data;
    public int size;
    public int capacity;
    public static final int DEFAULT_CAPACITY = 10;
    public Heap(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
    }
    public Heap() {
        this.capacity = DEFAULT_CAPACITY;
        this.data = new int[DEFAULT_CAPACITY];
    }

    public void initData(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
            size++;
        }
    }

    public void createHeap() {
        for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, size);
        }
    }

    /**
     * @param parent 父节点
     * @param size 堆的大小
     */
    public void siftDown(int parent, int size) {
        int child = parent * 2 + 1;
        while (child < size) {
            if(child + 1 < size && data[child] < data[child + 1]) {
                child++;
            }
            if (data[child] > data[parent]) {
                swap(data, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void push(int val) {
        if (isFull()) {
            this.capacity = capacity + (capacity >> 1);
            data = Arrays.copyOf(data, data.length + (data.length >> 1));
        }
        data[size] = val;
        siftUp(size++);
    }

    private void swap(int[] data, int left, int right) {
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;
    }

    public void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (data[child] > data[parent]) {
                swap(data, child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return size == capacity;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(String.format(i == size - 1 ? "%d" : "%d, ", data[i]));
        }
        return sb.append("]").toString();
    }

    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("堆为空");
        }
        int val = data[0];
        swap(data, 0, --size);
        siftDown(0, size);
        return val;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("堆为空");
        }
        return data[0];
    }

    public void sort() {
        int end = size - 1;
        while (end > 0) {
            swap(data, 0, end);
            siftDown(0, end--);
        }
    }

    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        PriorityQueue<Integer> p = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < k; ++i) {
            p.offer(arr[i]);
        }

        for (int i = k; i < arr.length; ++i) {
            int peekVal = p.peek();
            if (arr[i] < peekVal) {
                p.poll();
                p.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; ++i) {
            ret[i] = p.poll();
        }
        return ret;
    }
}
